
#include <iostream>
#include <string>
#include <vector>

using namespace std;

namespace BSTree
{
    template<class K>
    struct KTreeNode
    {
        K _key;
        KTreeNode<K>* _left;
        KTreeNode<K>* _right;

        KTreeNode(const K& key)
            :_key(key)
             ,_left(nullptr)
             ,_right(nullptr)
        {}
    };

    template<class K>
    class KeyTree
    {
        typedef KTreeNode<K> Node;
    public:
        
        bool find(const K& key)
        {
            Node* cur = _root;

            while (cur)
            {
                if (cur->_key < key)
                {
                    cur = cur->_right;
                }
                else if (cur->_key > key)
                {
                    cur = cur->_left;
                }
                else 
                {
                    return true;
                }
            }

            return false;
        }


        bool insert(const K& key)
        {
            if (_root == nullptr)
            {
                _root = new Node(key);
                return true;
            }

            Node* cur = _root;
            Node* parent = nullptr;

            while (cur)
            {
                if (cur->_key < key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if (cur->_key > key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else 
                {
                    return false;
                }
            }

            cur = new Node(key);
            if (parent->_key < key)
            {
                parent->_right = cur;
            }
            else 
            {
                parent->_left = cur;
            }

            return true;
        }

        bool erase(const K& key)
        {
            Node* cur = _root;
            Node* parent = nullptr;

            while (cur)
            {
                if (cur->_key > key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else if (cur->_key < key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else 
                {
                    if (cur->_left == nullptr)
                    {
                        if (cur == _root)
                        {
                            _root = cur->_right;
                        }
                        else 
                        {
                            if (parent->_left == cur)
                            {
                                parent->_left = cur->_right;
                            }
                            else 
                            {
                                parent->_right = cur->_right;
                            }
                        }

                        delete cur;
                        return true;
                    }
                    else if (cur->_right == nullptr)
                    {
                        if (cur == _root)
                        {
                            _root = cur->_left;
                        }
                        else 
                        {
                            if (parent->_left == cur)
                            {
                                parent->_left = cur->_left;
                            }
                            else 
                            {
                                parent->_right = cur->_left;
                            }
                        }

                        delete cur;
                        return true;
                    }
                    else 
                    {
                        Node* min = cur->_right;
                        Node* minparent = cur;

                        while (min->_left)
                        {
                            minparent = min;
                            min = min->_left;
                        }

                        swap(cur->_key, min->_key);
                        if (minparent->_right == min)
                        {
                            minparent->_right = min->_right;
                        }
                        else 
                        {
                            minparent->_left = min->_right;
                        }

                        delete min;
                        return true;
                    }
                }
            }

            return false;
        }

        void InOrder()
        {
            _InOrder(_root);
            cout << endl;
        }

        KeyTree() = default;

        KeyTree(const KeyTree<K>& tree)
        {
            _root = _copy(tree._root);
        }

        ~KeyTree()
        {
            destory(_root);
        }

        KeyTree<K>& operator=(KeyTree<K> tree)
        {
            swap(_root, tree._root);
            return *this;
        }

        bool findR(const K& key)
        {
            return _findR(_root, key);
        }

        bool insertR(const K& key)
        {
            return _insertR(_root, key);
        }

        bool eraseR(const K& key)
        {
            return _eraseR(_root, key);
        }

    private:
        
        bool _eraseR(Node*& root, const K& key)
        {
            if (root == nullptr)
            {
                return false;
            }

            if (root->_key > key)
            {
                return _eraseR(root->_left, key);
            }
            else if (root->_key < key)
            {
                return _eraseR(root->_right, key);
            }
            else 
            {
                Node* del = root;

                if (root->_left == nullptr)
                {
                    root = root->_right;
                }
                else if (root->_right == nullptr)
                {
                    root = root->_left;
                }
                else 
                {
                    Node* min = root->_right;
                    while (min->_left)
                    {
                        min = min->_left;
                    }

                    swap(root->_key, min->_key);
                    return _eraseR(root->_right, key);
                }

                delete del;
                return true;
            }
        }

        bool _insertR(Node*& root, const K& key)
        {
            if (root == nullptr)
            {
                root = new Node(key);
                return true;
            }

            if (root->_key < key)
                return _insertR(root->_right, key);
            else if (root->_key > key)
                return _insertR(root->_left, key);
            else 
                return false;
        }

        bool _findR(Node* root, const K& key)
        {
            if (root == nullptr)
            {
                return false;
            }

            if (root->_key < key)
                return _findR(root->_right, key);
            else if (root->_key > key)
                return _findR(root->_left, key);
            else 
                return true;
        }

        void destory(Node* root)
        {
            if (root == nullptr)
                return;

            destory(root->_left);
            destory(root->_right);
            delete root;
        }

        Node* _copy(Node* root)
        {
            if (root == nullptr)
            {
                return nullptr;
            }

            Node* cur = new Node(root->_key);
            cur->_left = _copy(root->_left);
            cur->_right = _copy(root->_right);

            return cur;
        }

        void _InOrder(Node* root)
        {   
            if (root == nullptr)
                return;

            _InOrder(root->_left);
            cout << root->_key << ' ';
            _InOrder(root->_right);
        }

        Node* _root = nullptr;
    };

    template<class K, class V>
    struct KVTreeNode
    {
        K _key;
        V _value;
        KVTreeNode<K, V>* _left;
        KVTreeNode<K, V>* _right;

        KVTreeNode(const K& key, const V& value)
            :_key(key)
             ,_value(value)
             ,_left(nullptr)
             ,_right(nullptr)
        {}
    };

   
    template<class K, class V>
    class KVTree
    {
        typedef KVTreeNode<K, V> Node;
    public:
        
        Node* find(const K& key)
        {
            Node* cur = _root;

            while (cur)
            {
                if (cur->_key < key)
                {
                    cur = cur->_right;
                }
                else if (cur->_key > key)
                {
                    cur = cur->_left;
                }
                else 
                {
                    return cur;
                }
            }

            return nullptr;
        }


        bool insert(const K& key, const V& value)
        {
            if (_root == nullptr)
            {
                _root = new Node(key, value);
                return true;
            }

            Node* cur = _root;
            Node* parent = nullptr;

            while (cur)
            {
                if (cur->_key < key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if (cur->_key > key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else 
                {
                    return false;
                }
            }

            cur = new Node(key, value);
            if (parent->_key < key)
            {
                parent->_right = cur;
            }
            else 
            {
                parent->_left = cur;
            }

            return true;
        }

        bool erase(const K& key)
        {
            Node* cur = _root;
            Node* parent = nullptr;

            while (cur)
            {
                if (cur->_key > key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else if (cur->_key < key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else 
                {
                    if (cur->_left == nullptr)
                    {
                        if (cur == _root)
                        {
                            _root = cur->_right;
                        }
                        else 
                        {
                            if (parent->_left == cur)
                            {
                                parent->_left = cur->_right;
                            }
                            else 
                            {
                                parent->_right = cur->_right;
                            }
                        }

                        delete cur;
                        return true;
                    }
                    else if (cur->_right == nullptr)
                    {
                        if (cur == _root)
                        {
                            _root = cur->_left;
                        }
                        else 
                        {
                            if (parent->_left == cur)
                            {
                                parent->_left = cur->_left;
                            }
                            else 
                            {
                                parent->_right = cur->_left;
                            }
                        }

                        delete cur;
                        return true;
                    }
                    else 
                    {
                        Node* min = cur->_right;
                        Node* minparent = cur;

                        while (min->_left)
                        {
                            minparent = min;
                            min = min->_left;
                        }

                        swap(cur->_key, min->_key);
                        if (minparent->_right == min)
                        {
                            minparent->_right = min->_right;
                        }
                        else 
                        {
                            minparent->_left = min->_right;
                        }

                        delete min;
                        return true;
                    }
                }
            }

            return false;
        }

        void InOrder()
        {
            _InOrder(_root);
            cout << endl;
        }

        KVTree() = default;

        KVTree(const KVTree<K, V>& tree)
        {
            _root = _copy(tree._root);
        }

        ~KVTree()
        {
            destory(_root);
        }

        KVTree<K, V>& operator=(KVTree<K, V> tree)
        {
            swap(_root, tree._root);
            return *this;
        }

    private:
        
        void destory(Node* root)
        {
            if (root == nullptr)
                return;

            destory(root->_left);
            destory(root->_right);
            delete root;
        }

        Node* _copy(Node* root)
        {
            if (root == nullptr)
            {
                return nullptr;
            }

            Node* cur = new Node(root->_key, root->_value);
            cur->_left = _copy(root->_left);
            cur->_right = _copy(root->_right);

            return cur;
        }

        void _InOrder(Node* root)
        {   
            if (root == nullptr)
                return;

            _InOrder(root->_left);
            cout << root->_key << ' ' << root->_value << ' ' << '|' << ' ';
            _InOrder(root->_right);
        }

        Node* _root = nullptr;
    };
}
